Fingerprint sensing and matching is a reliable and widely used technique for personal identification or verification. In particular, a common approach to fingerprint identification involves scanning a sample fingerprint or an image thereof and storing the image and/or unique characteristics of the fingerprint image. The characteristics of a sample fingerprint may be compared to information for reference or enrolled fingerprints already in a database to determine proper identification of a person, such as for verification purposes.
A significant advance in the area of fingerprint sensing is disclosed in U.S. Pat. No. 5,940,526 to Setlak et al. and assigned to the assignee of the present invention. The patent discloses an integrated circuit fingerprint sensor including an array of RF sensing electrodes to provide an accurate image of the fingerprint friction ridges and valleys. More particularly, the RF sensing permits imaging of live tissue just below the surface of the skin to reduce spoofing, for example. The entire contents of the Setlak et al. patent are incorporated herein by reference.
Image mosaicing is a major area of research in image processing and computer vision as noted by L. Brown in A survey of image registration techniques, ACM Computing Surveys, vol. 24, no. 4, pp. 325-376, 1992. It can be defined as follows. Two or more images are given with each one of them capturing only a partial view of some data of interest. The purpose of mosaicing is to generate an image providing a composite view, which is the union of the partial views. At the core of mosaicing is a process involving alignment or registration of two images. The performance of the alignment process relates to the overall performance of mosaicing. The major goal of mosaicing is the generation of composite data sets (images, or feature sets) that are as seamless as possible.
It is also possible to perform mosaicing at the feature level, instead of the image level. That is, a feature set is extracted from each input image. These sets are then combined to generate a composite feature set corresponding to their union.
There have been several research efforts on mosaicing of fingerprint data. For example, Ratha et al. in Image mosaicing for rolled fingerprint construction, Proc. Int. Conf. Pattern Recognition, vol. 2, pp. 1651-1653, 1998 presents a method for mosaicing of fingerprint images obtained during a finger rolling motion. Jain and Ross in Fingerprint mosaicking, Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, Orlando, Fla., 2002 disclose a technique for mosaicing of fingerprint images using minutiae for alignment. Yau et al. in On fingerprint template synthesis, Proc. Sixth Int. Conf. on Control, Automation, Robotics and Vision, Singapore, 2000, and U.S. Pat. No. 6,546,122 to Russo considered fingerprint mosaicing at the feature level using minutia sets.
In all of the above cases, mosaicing is performed at the physical level. In other words, the data sets (images or feature sets) are physically fused to produce a composite data set.
A fundamental limitation of physical mosaicing is that it fails to explicitly account for the uncertainty of the alignment process. Accounting for alignment uncertainty is not needed if the goal of mosaicing is, for example, subjective analysis by humans. However, it is generally of significant importance if the goal of mosaicing is to provide data to an automated process such as matching. While this applies to mosaicing in general, uncertainty accommodation is of particular importance in the context of fingerprint matching. This is because alignment of fingerprint images can be associated with considerable amounts of uncertainty. The high alignment uncertainty is due to a number of factors such as poor image quality and small overlapping area. More importantly, it is because the transformation model used for alignment is simpler than the actual one; it either does not account for local non-linear deformations, or only partially accounts for it.
Accounting for alignment uncertainty may be very difficult in the case of physical mosaicing. FIGS. 1A-1C and 2 show an example of physical mosaicing as in the prior art. The input set, which includes three images 31-33, is shown in FIGS. 1A-1C. These images 31-33 are aligned, and the alignment information is used to construct the physical mosaic image 34 in FIG. 2. The presence of slight ridge misalignment is seen in the upper central area of the mosaic. Such misalignment can be problematic to the matching process.
There has also been a recent drive in the biometrics industry to reduce the cost of biometric sensors. This drive is fueled by the need to develop cost-effective biometric solutions needed for large-scale deployment in consumer-electronic products, such as cell phones, PDAs, and notebooks. In particular, the fingerprint biometrics industry has been dropping sensor cost through reducing sensor size. Reduction of sensor size is driven not only by the desire to reduce cost, but also by the need to have sensors with a small form factor for integration into small devices, such as cell phones and PDAs.
For example, AuthenTec, Inc. of Melbourne, Fla., and the assignee of the present invention, has produced a small touch sensor whose sensing area is only 6.5 mm×6.5 mm (AES 3500). This area is less than 20% that of a typical fingerprint sensor. Further significant reduction in sensor size reduces the amount of available fingerprint information to the point where the touch mode of operation becomes very difficult, or even impossible, to support.
This shortcoming can be addressed by adopting a dynamic mode of operation, where a finger slides across the sensor, instead of just touching it. The slide operation allows the fingerprint system to gather information about a fingerprint area that is significantly larger than the physical area of the sensor. The slide sensor has a very small length along the direction of finger motion and a typical length normal to it. The touch mode of operation is a simple one, involving the downward movement of a finger until it gets in contact with the sensor surface, keeping the finger in contact with the sensor for a reasonable amount of time until the sensor acquires an image of the fingerprint, and upward movement of the finger away from the sensor.
The slide mode of operation is a slightly more complicated one. It involves downward movement of the finger until a lower part of it gets in contact with the slide sensor, sliding the finger across the sensor for a reasonable distance, or until contact is lost, and upward movement of the finger away from the sensor.
Processing of fingerprint data provided by a slide sensor poses significant algorithmic challenges. The slide data are provided as a sequence of images, referred to as image slices, or simply slices. The dimensions of each slice are the same as that of the sensor. The sequence of slices corresponds to successive areas of the fingerprint. For recognition purposes, it may be highly desirable that consecutive slices represent overlapping areas of the fingerprint. Slice overlapping permits aligning consecutive slices, and subsequently obtaining information about the big fingerprint picture from the given slices.
FIG. 3B shows a sequence of slices, S={s1, . . . , sn} mapped to a fingerprint as in the prior art, along with the speed profile 35 of the sliding finger 36 (finger speed as a function of time of FIG. 3A). The extent of overlap between consecutive slices is inversely proportional to the speed of the finger. Thus, the overlap information can be used to estimate the speed profile. To maintain overlap, the slide speed of the finger 36 should not exceed a certain limit, which is proportional to the scanning rate of the sensor. If the speed does exceed the limit within a certain time interval, then consecutive slices obtained within this interval will have gaps between them. This scenario is depicted in FIGS. 4A and 4B. Slices obtained within the over-speeding time interval cannot be accurately aligned with other slices. The only possibility is obtaining crude alignment by performing interpolation of the speed profile.
The mapping between a slice and its location on the fingerprint is not necessarily a simple one. FIGS. 3B and 4B implicitly assume that each slice is captured “instantaneously”. Accordingly, the rectangular slice obtained by the slide sensor maps to an identical rectangular area on the fingerprint. The assumption of an instantaneous snapshot is reasonable, only if the sensor scanning rate is significantly high relative to the slide speed. Otherwise, the slice-to-fingerprint mapping will become a more involved one. For example, assume that the slice is captured column by column, where each column is captured almost instantaneously. In such a case, the rectangular slice maps to a parallelogram, where the extent of deviation from a rectangle is proportional to the slide speed. This is demonstrated in FIGS. 5A and 5B. On the other hand, consider the case where the scanning is performed in a row wise fashion, such that the scan of each row is done almost instantaneously. In such a case, the slice rectangle maps to another rectangle that is stretched along the direction of motion, where the extent of stretching is proportional to the slide speed (see FIGS. 6A and 6B). Prime and multiple prime notation is used to indicate similar elements in FIGS. 4A through 6B.
The majority of fingerprint recognition systems rely on touch sensors. It is only recently that slide sensors have been used for fingerprint recognition. Note that slide sensors are also commonly known as swipe or sweep sensors. A key component of any slide-sensor system is preprocessing of the slide data, represented as a sequence of slices, before using it for matching. Virtually, all existing systems attempt to reconstruct a fingerprint image from the sequence of slices generated by the slide sensor.
For example, U.S. Pat. Nos. 6,289,114 and 6,459,804 to Mainguet describe a method for image reconstruction from slices obtained using a thermal slide sensor. In this work, image slices are stitched together to form a fingerprint image. Stitching is based on alignment of consecutive slices using correlation. Published U.S. application U.S. 2003-0123714 A1 to O'Gorman et al. discloses another approach for image reconstruction. Some highlights of this work can be outlined as follows. The sequence of images provided by the slide sensor is processed to generate an image of the fingerprint. However, only a subset of the image, which they define as a slice, is used in the reconstruction. This sub-image has the same number of columns as the original image but fewer rows. Correlation is based on a sub-image of the slice, which is referred to as a frame. This sub-image has the same number of columns as the sensor but fewer rows than the slice. A frame in a slice is correlated with similar frames in an adjacent slice to determine the extent of overlap between them.
Apparent stretching of image slices due to slide speed is accounted for through removing some image rows. Some characteristics of the slide process can be used to differentiate between a real finger and a fake one (e.g., average speed).
Published U.S. patent application No. 2003-0126448 A1 to Russo discloses a method for reconstructing an image from image slices, based on normalized cross correlation. Statistics of the acquisition process such as angle of slide direction and slide speed can be embedded in the image.
Published U.S. patent application No. 2002-0067845 A1 to Griffis describes a method for image reconstruction using a line sensor. The sensor is augmented with few sensing elements normal to the sensing line. These auxiliary elements are used to estimate finger speed, which is needed for image reconstruction from the acquired sequence of one-line slices. Finally, Maltoni et al. in Handbook of fingerprint recognition, Springer-Verlag, New York, 2003 propose an image reconstruction method from slide data. The method is based on first calculating the horizontal and vertical shifts between consecutive slices. The profiles of these shifts are smoothed and then subsequently used for image reconstruction.
The approaches described above process the slide data to construct a fingerprint image. Representing slide data using an image is fundamentally limited in its ability to accommodate the uncertainties involved in the image reconstruction process. These uncertainties mainly correspond to errors in the alignment of consecutive slices. For example, assume that the relative transformation between two consecutive slices is described by vertical and horizontal translations. If the resolution of the alignment is at the pixel level, then there is a fundamental error of plus or minus half a pixel both vertically and horizontally. Alignment uncertainty depends not only on image quantization, but also on a number of other factors. These factors include:
1. Image Noise: Alignment uncertainty is proportional to the amount of image noise.
2. Transformation Model Error: This refers to the difference between the assumed transformation model used for alignment and the actual one. The closer the assumed model to the actual one, the less the alignment uncertainty is. The price is paid in more complex and time-consuming alignment. For example, a transformation model that accounts for only two-dimensional translation is expected to have more alignment uncertainty than that which includes rotation as well as two-dimensional translation. The latter transformation model is expected to have more uncertainty than one that further accounts for local non-linear distortions.
3. Alignment Algorithm: This includes the criterion used to determine the alignment (e.g., sum of squared differences, normalized cross correlation, see L. Brown, A survey of image registration techniques, ACM Computing Surveys, vol. 24, no. 4, pp. 325-376, 1992.) Some criteria produce more accurate alignments than others. The algorithm also includes the strategy used to search the transformation space (e.g., coarse-to-fine searching versus flat searching).
4. Slide Speed: As mentioned earlier, the amount of overlap between consecutive slices depends on slide speed. Intuitively, the amount of information available for alignment is proportional to the amount of overlap. Thus, fundamentally, alignment uncertainty is proportional to slide speed. In the extreme case, the slide speed exceeds the limit for having overlap between consecutive slices (see FIGS. 4A and 4B). In such a case, alignment can only be determined coarsely through interpolation of the speed profile, which can significantly increase the uncertainty.
5. Image Content: Uniform fingerprint image areas, e.g., those composed of parallel ridges, can increase the amount of alignment uncertainty, whereas unique areas can reduce it. In general, alignment uncertainty is inversely proportional to image information content.
Another level of complication arises since the alignment is based on comparing consecutive, or very close, slices. Thus, alignment error accumulates as the image gets constructed. For example, let S={s1, . . . sn} be a sequence of slices, and U(si, sj) a measure of the alignment uncertainty between slices si and sj. Intuitively, U(s1, s3) is the accumulation of uncertainties U(s1, s2) and U(s2, s3). Similarly, U(s1, s4) is the accumulation of U(s1, s2), U(s2, s3) and U(s3, s4) and so on. The uncertainty reaches its maximum level between s1 and sn, U(s1, sn). From the above discussion, it can be seen that ignoring the uncertainty in the alignment among image slices can lead to significant degradation in performance of fingerprint recognition.